package java学习.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author 刘世锦
 * 2022-12-12 23:28:38	 当前时间
 */
//给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和
// targetSum 。如果存在，返回 true ；否则，返回 false 。 
//
// 叶子节点 是指没有子节点的节点。 
//
// 
//
// 示例 1： 
//
// 
//输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
//输出：true
//解释：等于目标和的根节点到叶节点路径如上图所示。
// 
//
// 示例 2： 
//
// 
//输入：root = [1,2,3], targetSum = 5
//输出：false
//解释：树中存在两条根节点到叶子节点的路径：
//(1 --> 2): 和为 3
//(1 --> 3): 和为 4
//不存在 sum = 5 的根节点到叶子节点的路径。 
//
// 示例 3： 
//
// 
//输入：root = [], targetSum = 0
//输出：false
//解释：由于树是空的，所以不存在根节点到叶子节点的路径。
// 
//
// 
//
// 提示： 
//
// 
// 树中节点的数目在范围 [0, 5000] 内 
// -1000 <= Node.val <= 1000 
// -1000 <= targetSum <= 1000 
// 
// Related Topics 树 深度优先搜索 广度优先搜索 二叉树 
// 👍 1064 👎 0

public class 路径总和{
	public static void main(String[] args) {
		Solution solution = new 路径总和().new Solution();
		
	}
//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {

	/** 复习  @author 刘世锦       1
	 *  @date  2023/2/2 9:25    /
	 *                         2
	 *
	 * _       7 2 1_
	 *
	 * _      27 22  18_
	 *
	 */
	public boolean hasPathSum(TreeNode root, int targetSum) {
		Queue<TreeNode> queue = new LinkedList<>();
		if (root!=null){
			queue.offer(root);
			while (!queue.isEmpty()){
				int size = queue.size();
				for (int i = 0; i < size; i++) {
					TreeNode node = queue.poll();
					// 叶子节点
					if (node.val==targetSum&&node.left==null&&node.right==null){
						return true;
					}
					if (node.left!=null){
						node.left.val+=node.val;
						queue.offer(node.left);
					}
					if (node.right!=null){
						node.right.val+=node.val;
						queue.offer(node.right);
					}
				}

			}



		}

		return false;

	}





	// 复习end





	public boolean hasPathSum1(TreeNode root, int targetSum) {

		if (root==null) {
			return false;
		}
		if (root.left==null&&root.right==null) {
			return targetSum - root.val == 0;
		}
		if(hasPathSum(root.left,targetSum-root.val)) {
			return true;
		}
		if(hasPathSum(root.right,targetSum-root.val)) {
			return true;
		}
		return false;
	}
	public boolean hasPathSum2(TreeNode root, int targetSum) {

		if (root==null) {
			return false;
		}
//		targetSum-=root.val;
		if (root.left==null&&root.right==null) {
			return targetSum  == root.val;
		}
		if (root.left!=null){
			// 若左子树有path=Sum 直接true
			boolean b = hasPathSum(root.left, targetSum - root.val );
			if (b){
				return true;
			}
		}
		if (root.right!=null){
			// 若右子树有path=Sum 直接true
			boolean b = hasPathSum(root.right,targetSum - root.val );
			if (b){
				return true;
			}
		}
		return false;
	}

		/**
         * 1. 先求出 每条路径总和
         * 2. 判断是否存在该 target
         *
         * _  8 11  _
         * 5 4
         * _ _
         * 5->4 ->11
         *
         */
    public boolean hasPathSumBFS(TreeNode root, int targetSum) {
    	boolean res = false;
//		ArrayList<Integer> list = new ArrayList<>();
		Queue<TreeNode> queue = new LinkedList<>();
		Queue<Integer> integerQueue = new LinkedList<>();

		if (root!=null){
    		queue.offer(root);
    		integerQueue.offer(root.val);
    		while (!queue.isEmpty()){
				TreeNode node = queue.poll();
				Integer nodeInteger = integerQueue.poll();
				if (node.left==null&&node.right==null){
//					list.add(nodeInteger);
					if (nodeInteger==targetSum){
						res = true;break;
					}
				}
				if (node.left!=null){
					queue.offer(node.left);
					integerQueue.offer(node.left.val+nodeInteger);
				}
				if (node.right!=null){
					queue.offer(node.right);
					integerQueue.offer(node.right.val+nodeInteger);
				}
			}
		}
//		for (Integer integer : list) {
//			if (integer==targetSum){
//				res = true;break;
//			}
//		}
//		System.out.println(list);
		return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
